package org.zdw.data.structure.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树是一种非线性数据结构，属于树结构，最大的特点就是度为2，也就是每个节点只有一个左子树和一个右子树。
 * 二叉树的操作主要为创建，先序遍历，中序遍历，后序遍历。还有层次遍历。
 * 遍历有两种方式，一是采用递归的方式，二是采用转换为栈进行遍历，对二叉树的遍历本质上市将非线性结构转换为线性序列。
 */
public class BinaryTree<E> {

    /**
     * 生命节点类
     * @param <E>
     */
    public static class Node<E>{
        Node<E> left = null;
        Node<E> right = null;

        E data = null;

        public Node(E data){
            this.data = data;
            left = null;
            right = null;
        }

        public Node(){}
    }

    private Node<E> root = null;//根节点
    private List<Node<E>> list = null;//节点列表，用于将数组元素转化为节点

    public Node<E> getRoot(){
        return this.root;
    }

    public void createTreeByArray(E[] array){
        list = new ArrayList<Node<E>>();
        //将数组添加到节点列表
        for (int i = 0; i < array.length; i++) {
            list.add(new Node(array[i]));
        }

        System.out.println("头节点->" + list.get(0).data);
        this.root = new Node(list.get(0).data); //根节点

        for (int j = 0; j < (array.length/2) ; j++){
            list.get(j).left = list.get(2*j+1);
            System.out.println("节点" + list.get(j).data + "左子树 ->" + list.get(j * 2 + 1).data);
            list.get(j).right = list.get(2*j+2);
            System.out.println("节点" + list.get(j).data + "右子树 ->" + list.get(j * 2 + 2).data);
        }
    }

    /**
     * 先序遍历
     * @param root
     */
    public void indorder(Node<E> root){
        if(root == null){
            return;
        }
        System.out.println(root.data);
        indorder(root.left);  //递归输出左子树
        indorder(root.right); //递归遍历右子树
    }

    /**
     * 先序遍历
     * @param root
     */
    public void inOrderTraverse(Node<E> root){
        if(root == null){
            return;
        }
        inOrderTraverse(root.left);  //递归输出左子树
        System.out.println(root.data);
        inOrderTraverse(root.right); //递归遍历右子树
    }

    /**
     * 先序遍历
     * @param root
     */
    public void postOrderTraverse(Node<E> root){
        if(root == null){
            return;
        }
        postOrderTraverse(root.left);  //递归输出左子树
        postOrderTraverse(root.right); //递归遍历右子树
        System.out.println(root.data);
    }

    public static void main(String[] args) {
        BinaryTree<String> createTreeByArray = new BinaryTree<String>();
        String[] arrays = {"A","B","C","D","E","F","G"};
        createTreeByArray.createTreeByArray(arrays);
        System.out.println("===============================");
        createTreeByArray.postOrderTraverse(createTreeByArray.list.get(0));
    }
}
